package com.colter.project.years.question2016.month07;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * You are given two integer arrays nums1 and nums2 sorted in ascending order
 * and an integer k.
 * 
 * Define a pair (u,v) which consists of one element from the first array and
 * one element from the second array.
 * 
 * Find the k pairs (u1,v1),(u2,v2) ...(uk,vk) with the smallest sums.
 * 
 * Example 1: Given nums1 = [1,7,11], nums2 = [2,4,6], k = 3
 * 
 * Return: [1,2],[1,4],[1,6]
 * 
 * The first 3 pairs are returned from the sequence:
 * [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6] Example 2: Given
 * nums1 = [1,1,2], nums2 = [1,2,3], k = 2
 * 
 * Return: [1,1],[1,1]
 * 
 * The first 2 pairs are returned from the sequence:
 * [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3] Example 3: Given nums1
 * = [1,2], nums2 = [3], k = 3
 * 
 * Return: [1,3],[2,3]
 * 
 * All possible pairs are returned from the sequence: [1,3],[2,3]
 * 
 * @author user
 *
 */
public class Test1GetK {
	public static void main(String[] args) {
		Test1GetK g = new Test1GetK();
		int[] nums1 = new int[] { 1, 2, 3 };
		int[] nums2 = new int[] { 1, 2, 3, 4 };
		int k = 3;
		System.out.println(g.kSmallestPairs(nums1, nums2, k));
	}

	public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
		List<IntArray> list = new ArrayList<>();
		for (int a : nums1) {
			for (int b : nums2) {
				list.add(new IntArray(a, b));
			}
		}

		IntArray[] array = list.toArray(new IntArray[list.size()]);
		Arrays.sort(array);

		List<int[]> result = new ArrayList<>();
		if (array.length > k) {
			for (int i = 0; i < k; i++) {
				result.add(array[i].getArray());
			}
		} else {
			for (IntArray arr : array) {
				result.add(arr.getArray());
			}
		}

		return result;

	}
}

class IntArray implements Comparable<IntArray> {
	private int[] array;
	private int sum;

	public int[] getArray() {
		return array;
	}

	public void setArray(int[] array) {
		this.array = array;
	}

	public int getSum() {
		return sum;
	}

	public void setSum(int sum) {
		this.sum = sum;
	}

	public IntArray(int a, int b) {
		array = new int[2];
		array[0] = a;
		array[1] = b;
		sum = a + b;
	}

	@Override
	public int compareTo(IntArray o) {
		if (this.sum > o.sum) {
			return 1;
		} else if (this.sum < o.sum) {
			return -1;
		}
		return 0;
	}
}
